#include <stdio.h>
#include <stdlib.h>
#define bool unsigned int
#define true 1
#define false 0
#define none 2

int GetDigitSum(int number)
{
	int sum = 0;
	while (number > 0)
	{
		sum += number % 10;
		number /= 10;
	}
	return sum;
}
int MovingCountCore(int threshold, int rows, int cols, int row, int col, bool* visit)
{
	int count = 0;
	if (row >= 0 && row < rows && col >= 0 && col < cols && GetDigitSum(row) + GetDigitSum(col) <= threshold && !visit[cols * row + col])
	{
		visit[cols * row + col] = 1;
		count = 1 + MovingCountCore(threshold, rows, cols, row + 1, col, visit) +
			MovingCountCore(threshold, rows, cols, row - 1, col, visit) +
			MovingCountCore(threshold, rows, cols, row, col + 1, visit) +
			MovingCountCore(threshold, rows, cols, row, col - 1, visit);
	}
	return count;
}
int MovingCount(int threshold, int rows, int cols)
{
	bool* visit;
	int count;
	int i = 0;
	if (rows <= 0 || cols <= 0 || threshold < 0)
		return false;
	visit = (bool*)malloc(sizeof(bool) * (rows * cols));
	for (i = 0; i < rows * cols; i++)
	{
		visit[i] = 0;
	}
	count = MovingCountCore(threshold, rows, cols, 0, 0, visit);
	free(visit);
	return count;
}

int main()
{
	printf("%d", MovingCount(1, 2, 2));
}
